% % % % % % % % % % % % % % % % % % % % % 
% 
% Alpha Beta Prunning : Gruppe G
% 
% % % % % % % % % % % % % % % % % % % % % 

function [weight, A]=negaMAX(A, depth, color, alpha, beta, endgame)

% if depth=0 return weight
if(depth==0)
    weight = evalfunc(A, color, endgame);
    return;
end

% Get matrix of all valid fields
ValidFields = GetValidFields(A, color);

% Position and number of valid fields/moves
[row, column] = find(ValidFields);
numValidFields = sum(ValidFields(:));

if numValidFields == 0   % no possible moves
    % test if call comes form our player
    if nargout == 2
        % We cannot make a valid move. Return unchanged board to tournament
        % server. 
        weight = [];
        return;
    end

    % There is no valid move so it is the other player's turn.
    weight = -negaMAX(A , depth-1, -color, -beta, -alpha, endgame);
    return;
end
    
% Find the best currentMove
bestMove = zeros(2,1);


for CurrentMoveIdx = 1:numValidFields

    % calculate new board
    currentA = make_move(A, row(CurrentMoveIdx), column(CurrentMoveIdx), color);
    % recursive negaMAX -> next player
    weight = -negaMAX(currentA, depth-1, -color, -beta, -alpha, endgame);


    if weight>alpha
        alpha = weight;
        bestMove = [row(CurrentMoveIdx); column(CurrentMoveIdx)];
    end
    if weight>=beta
        weight = beta;
        return; % beta-cut
    end

    
end


%  Make the best move and return new board. 
if nargout == 2 
        A = make_move(A, bestMove(1), bestMove(2), color);
end


weight = alpha;

end




